/**
 * 最长上升子序列
 * @param {Array} arr number[]
 */
function longestIncreasingSubSequence(arr) {
  const stack = [];
  const resultMatrix = [[]];

  for (let i = 0; i < arr.length; i++) {
    let pos = _search(stack, arr, i);
    stack[pos] = i;
    resultMatrix[i] = stack.map((j) => j);
  }

  const result = [];
  let k = resultMatrix.length - 1;
  for (let j = stack.length - 1; j >= 0; j--) {
    while (
      j < stack.length - 1 &&
      resultMatrix[k][j] > resultMatrix[k][j + 1]
    ) {
      k--;
    }
    result[j] = resultMatrix[k][j];
  }

  return result.map((d) => arr[d]);
}

/**
 * 找到stack上可以插入arr[i]的位置
 */
function _search(stack, arr, i) {
  /* O(n) */
  // let cur = 0;
  // while (cur < stack.length && arr[stack[cur]] < arr[i]) {
  //   cur++;
  // }
  // return cur;

  /* O(logn) */
  let left = 0;
  let right = stack.length;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[i] < arr[stack[mid]]) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }

  return left;
}

longestIncreasingSubSequence([10, 20, 30, 40, 50, 60, 70, 9, 31, 61, 11, 32]);
